\documentclass[12pt]{article}
\usepackage{graphicx}
\begin{document}

\begin{titlepage}
\Huge
\centerline{Exercise 5}

\vspace{2 mm}

\Large
\centerline{Heat Relaxation}
\vspace{5 mm}
\centerline{Steffen Lammel, Matthias Heisler}

\centerline{Group: introhpc00}
\clearpage
\end{titlepage}
\tableofcontents
\clearpage
\section{Sequential Implementation} \label{sec:seq}
The solution of this exercise can be found in the folder ex05-1. The solution itself consists out of three files, which are:
\begin{itemize}
\item The sourcefile heatrelax.c.
\item A makefile to build the executable (output: heatrelax).
\item And a shell-script,which will execute the compiled program.
\end{itemize} 
The following seven figures depict the behaviour of the program, respectively for selected iteration steps (after 0, 5, 10, 15, 25, 50, 75, 100 iterations).

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result0.pdf}
\caption{Init-state}
\label{init}
\end{figure}
 
The figure \ref{init} shows the init state of the heat relaxation. All we see is a small stripe which has been set statically to 127.

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result5.pdf}
\caption{Status after 5 iterations}
\label{iter5}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result10.pdf}
\caption{Status after 10 iterations}
\label{iter10}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result15.pdf}
\caption{Status after 15 iterations}
\label{iter15}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result25.pdf}
\caption{Status after 25 iterations}
\label{iter25}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result50.pdf}
\caption{Status after 50 iterations}
\label{iter50}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result75.pdf}
\caption{Status after 75 iterations}
\label{iter75}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-1/result100.pdf}
\caption{Status after 100 iterations}
\label{iter100}
\end{figure}

The figure \ref{iter5} shows the spreading of the heat over the plate after 5 iterations. The next figure \ref{iter10} shows the heat distribution after 10 iterations. We see that the heat is spreading over the plate.
The next figures from figure \ref{iter15} up to the figure \ref{iter75} depict the same like the figures before.\\
The last figure \ref{iter100} shows the last status that is simulated via the program. We see that this is the current maximum of the heat distribution. But we see that the heat will probably spread further if we raise the amount of iterations.\\

\clearpage
\section{Experiments} \label{sec:exp}
\begin{table}[hc]
\begin{tabular}{|l|l|l|l|}
\hline
Grid Size & Time/Iteration [sec] & GFLOPs & Flop total\\
\hline
\hline
127$\times$127 & 0.000197 & 0.573869 & 11290300.00\\
\hline
512$\times$512 & 0.002872 & 0.638977 & 183500800.00\\
\hline
1024$\times$1024 & 0.011365 & 0.645840 & 734003200.00\\
\hline
2048$\times$2048 & 0.064885 & 0.452494 & 2936012800.00\\
\hline
4096$\times$4096 & 0.190257 &
617272658.036275 & 11744051200.00\\
\hline
\end{tabular}
\caption{Measurement results for exercise 5.2}
\label{tab:meas}
\end{table}

The measurement results for the exercise 5.2 are depicted in the table \ref{tab:meas}. This measurement has been done by using the program from exercise 5.1. To avoid debug output the program has been changed. To suppress this output the debug flag in the source file has been set to zero. To calculate the results depicted in the second column of table 1, 100 iterations have been used for each grid size.

\begin{figure}[h]
\centering
\includegraphics[scale=1]{./ex05-2/result.pdf}
\caption{Measurment results}
\label{fig:measurment}
\end{figure}

To determine if this program is  computationally bound or memory-bound the results in table \ref{tab_meas} has been put into the figure  \ref{fig:measurment}. Here we see that the GFlops evolve almost constant while we increase the grid size. \\
So it could be possible that this program is memory-bound. Because of the almost constant GFlops.\\  
If we further inspect the formula which is used to calculate those results, we see that this formula results in an algorithm which uses a pseudo-random access onto the matrix elements (from cache view). This mean there are many cache misses during the calculation of the heat distribution. 
\clearpage
\section{Pre-considerations for parallelization}
\subsection{First approach}

\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-3/parallel01.pdf}
\caption{Example for pipelining}
\label{fig:pipe}
\end{figure}

In the previous section \ref{sec:exp} we have seen that the performance of this program depends on the accesses to the memory.\\If we now try to parallelize the most obvious way could be to do this by pipeline this problem. So that every node gets only a small slice out of the source matrix.\\Because of the dependencies between the single results of the final result we get a overlap which we have to communicate with the other (following nodes). This behaviour is depicted in figure \ref{fig:pipe}. On problem of this approach is that it only work if the heat spread from the upper matrix side to the lower side.\\
\subsection{Second approach}
\begin{figure}[ht]
\centering
\includegraphics[scale=0.8]{./ex05-3/parallel02.pdf}
\caption{Second approach (Split and Merge)}
\label{fig:merge}
\end{figure}
An other approach could be to split the source matrix into submatrices. These submatrices could be than calculated in the same way like we have done this for the "big" Matrix. In this case we also get an overlap, but this time we could handle it through adding the overlap during a synchronization step, while merging the submatrices back to one "big" Matrix. \\This approach seems to be less vulnerable than the first approach. The figure \ref{fig:merge} shows the intended behavior of this approach.
\end{document}